import com.sun.source.tree.Tree;

import java.util.ArrayList;
import java.util.List;

public class invertTree {
    /**
     * 翻转二叉树
     */
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(){}
        TreeNode(int val){
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode method(TreeNode root){
        // 1.特例
        if(root == null){
            return null;
        }
        // 2.递归调用
        // 定义节点暂存左节点，左节点此时再递归调用右节点
        TreeNode leftd=method(root.left);
        root.left=method(root.right);
        root.right=leftd;

        return root;
    }

    public static void main(String[] args) {
        invertTree i=new invertTree();

        TreeNode  root = i.new TreeNode(0);
        root.left = i.new TreeNode(1);
        root.right = i.new TreeNode(3);
        root.left.right = i.new TreeNode(2);
        root.right.left = i.new TreeNode(4);
        root.left.left = i.new TreeNode(5);

        TreeNode r = i.method(root);
        List<Integer> res=new ArrayList<>();
        in(r,res);

        // 输出结果
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        for(int j = 0;j<res.size();j++){
            sb.append(res.get(j));
            if(j<res.size() - 1){
                sb.append(", ");
            }
        }
        sb.append("]");
        System.out.println("sb = " + sb.toString());
    }

    public static void in(TreeNode node, List<Integer> list){
        if(node == null){
            return;
        }
        in(node.left,list);
        list.add(node.val);
        in(node.right,list);
    }
}
